Solution: First Unique Character in a String

Let's solve the First Unique Character in a String problem using the Knowing What to Track pattern.

Statement#

For a given string of characters, s, your task is to find the first non-repeating character and return its index. Return 1-1 if there’s no unique character in the given string.

Constraints:

  • Only lowercase english letters are accepted.
  • There are no spaces in the string.

Solution#

We need to keep track of the number of occurrences of each character in the string. To achieve this, we can use a hash map to store the character as a key and its number of occurrences in the string as its corresponding value.

The algorithm proceeds through the following steps:

  • Create a hash map and start a loop to traverse over the given input string.

  • At each iteration, we check if the current character is present in the hash map as a key.

    • If the key exists, we increment the value corresponding to this key character by 11.

    • Otherwise, add this new key-value pair in the hash map and set its value to 11.

  • Traverse over the input string to find the character in the hash map whose value equals 11.

    • If it exists, return the index of this character in the string. Otherwise, return 1-1.

The slide deck below illustrates the key steps of the solution.

svg viewer

1 of 32

svg viewer

2 of 32

svg viewer

3 of 32

svg viewer

4 of 32

svg viewer

5 of 32

svg viewer

6 of 32

svg viewer

7 of 32

svg viewer

8 of 32

svg viewer

9 of 32

svg viewer

10 of 32

svg viewer

11 of 32

svg viewer

12 of 32

svg viewer

13 of 32

svg viewer

14 of 32

svg viewer

15 of 32

svg viewer

16 of 32

svg viewer

17 of 32

svg viewer

18 of 32

svg viewer

19 of 32

svg viewer

20 of 32

svg viewer

21 of 32

svg viewer

22 of 32

svg viewer

23 of 32

svg viewer

24 of 32

svg viewer

25 of 32

svg viewer

26 of 32

svg viewer

27 of 32

svg viewer

28 of 32

svg viewer

29 of 32

svg viewer

30 of 32

svg viewer

31 of 32

svg viewer

32 of 32

Let’s look at the code for this solution below:

First Unique Character in a String

Time complexity#

The cost of traversing the length of the input string twice is O(2n)O(2n), which can be simplified to O(n)O(n).

Space complexity#

The space complexity of the algorithm above is O(1)O(1) because, at any time, a total of 2626 keys will be stored in the hash map. This makes it a constant space used to store the frequency of the characters’ occurrence.

First Unique Character in a String

Find All Anagrams in a String